package ctrip;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MinLength {

	private static int INF = Integer.MAX_VALUE;

	// dist[i][j]=INF<==>no edges between i and j
	private static int[][] dist;
	// the distance between i and j.At first,dist[i][j] is the weight of edge
	// [i,j]
	private static int[][] path;
	private static List<Integer> result = new ArrayList<Integer>();

	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int nodeCount;
		int[][] linjie;
		while (scanner.hasNext()) {
			nodeCount = scanner.nextInt();
			linjie = new int[nodeCount][nodeCount];
			path = new int[nodeCount][nodeCount];
			dist = new int[nodeCount][nodeCount];
			for (int i = 0; i < linjie.length; i++) {
				for (int j = 0; j < linjie[0].length; j++) {
					linjie[i][j] = scanner.nextInt();
				}
			}
			findCheapestPath(0, nodeCount - 1, linjie);
		}
		scanner.close();
	}

	public static void findCheapestPath(int begin, int end, int[][] matrix) {
		floyd(matrix);
		result.add(begin);
		findPath(begin, end);
		result.add(end);
//		int sum = 0;
		for (int i = 0; i < dist.length; i++) {
			for (int j = 0; j < dist[0].length; j++) {
				System.out.print("i : " + i + "-->" + j + " :" +  dist[i][j]);
			}
			System.out.println();
		}
	}

	public static void floyd(int[][] matrix) {
		int size = matrix.length;
		// initialize dist and path
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				path[i][j] = -1;
				dist[i][j] = matrix[i][j];
			}
		}
		for (int k = 0; k < size; k++) {
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (dist[i][k] != INF && dist[k][j] != INF
							&& dist[i][k] + dist[k][j] < dist[i][j]) {
						// dist[i][k] + dist[k][j] > dist[i][j]-->longestPath
						dist[i][j] = dist[i][k] + dist[k][j];
						path[i][j] = k;
					}
				}
			}
		}
	}
	public static void findPath(int i, int j) {
		int k = path[i][j];
		if (k == -1)
			return;
		findPath(i, k);
		result.add(k);
		findPath(k, j);
	}

}
